# 一种可以在O(1)时间内搜索的数据结构，叫做hash查找
'''
    HASH函数：
        一般来说，通过求余法获取每个需要存储的槽位置，但是这样可能会出现位置被占用的情况，也就是两个数求取余数时相同，这种情况完全可能发生的。要设法解决
    冲突解决：
        1. 开放寻址和线性探测，这样会出现聚集现象，也就是余数为1的数的槽会聚集在相邻的一部分，这个是显然的。这样其他占用的也需要跳过这些部分，查找时
        也需要跳过这些部分。当然可以把线性探测改一改，改成二次探测等等。具体看文档
        2. 允许每个槽保持对项的集合的引用，也就是说允许许多项存在hash表中的一个槽中
    实现：
        map 抽象数据类型定义如下。该结构是键与值之间的关联的无序集合。map 中的键都是唯一的，因此键和值之间存在一对一的关系。操作如下。
            - Map() 创建一个新的 map 。它返回一个空的 map 集合。
            - put(key，val) 向 map 中添加一个新的键值对。如果键已经在 map 中，那么用新值替换旧值。
            - get(key) 给定一个键，返回存储在 map 中的值或 None。
            - del 使用 `del map[key]` 形式的语句从 map 中删除键值对。
            - len() 返回存储在 map 中的键值对的数量。
            - in 返回 True 对于 `key in map` 语句，如果给定的键在 map 中，否则为False。
'''
class HashTable:
    def __init__(self):
        self.size = 11  # 字典的长度
        self.slots = [None] * self.size # 存储键项
        self.data = [None] * self.size  # 存储数据

    # hash函数实现简单的余数方法，解决冲突方法为加1rehash函数的线性探测
    def put(self,key,data):
        hashvalue = self.hashfunction(key,len(self.slots))  # 得到key对应的hash值

        if self.slots[hashvalue] == None:   # 为空槽，存入值
            self.slots[hashvalue] = key
            self.data[hashvalue] = data
        else:
            if self.slots[hashvalue] == key:    # 已经存入值
                self.data[hashvalue] = data # 替换数据
            else:   # 该位置已经被占了，解决冲突
                nextslot = self.rehash(hashvalue,len(self.slots))
                while self.slots[nextslot] != None and self.slots[nextslot] !=key:  # 等于key要替换的
                    nextslot = self.rehash(nextslot,len(self.slots))

                if self.slots[nextslot] == None:
                    self.slots[nextslot] = hashvalue
                    self.data[nextslot] = data

                else:
                    self.data[nextslot] = data  # 替换

    def hashfunction(self,key,size):    # size = 11
        return key % size

    def rehash(self,oldhash,size):
        return (oldhash + 1) % size # 欲取数可以避免超过索引

    def get(self,key):  # 返回这个值的data，其实就是通过slots列表找到key，再根据下标取到data列表对应的data
        startslot = self.hashfunction(key,len(self.slots))

        data = None
        stop = False
        found = False
        position = startslot
        while self.slots[position] != None and not found and not stop:
            if self.slots[position] == key:
                found = True
                data = self.data[position]
            else:
                position = self.rehash(position,len(self.slots))
                if position == startslot:   # 转了一圈没找到
                    stop = True
        return data

    def __getitem__(self, item):
        return self.get(item)

    def __setitem__(self, key, value):
        self.put(key,value)

def test():
    H = HashTable()
    H[54] = "cat"
    H[26] = "dog"
    H[93] = "lion"
    H[17] = "tiger"
    H[77] = "bird"
    H[31] = "cow"
    H[44] = "goat"
    H[55] = "pig"
    H[20] = "chicken"
    print(H.slots)
    print(H.data)
    print(H[54])
    print(H[66])

if __name__ == '__main__':
    test()